1. Field of Invention
The invention relates generally to methods and apparatus for converting a lightweight monitor to a heavyweight monitor in an object-based computing system. More particularly, the invention relates to methods and apparatus for atomically converting a lightweight monitor associated with a contended object to a corresponding heavyweight monitor in an object-based computing system.
2. Description of Relevant Art
Within an object-based environment, threads are often used to satisfy requests for services. A thread may be thought of as a xe2x80x9csketch padxe2x80x9d of storage resources, and is essentially a single sequential flow of control within a computer program. In general, a thread, or a xe2x80x9cthread of control,xe2x80x9d is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is xe2x80x9cpushedxe2x80x9d on the execution stack of the thread. When the method returns, or is deactivated, the activation is xe2x80x9cpoppedxe2x80x9d from the execution stack. Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
During the execution of an object-based program, a thread may attempt to execute operations that involve multiple objects. On the other hand, multiple threads may attempt to execute operations that involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
Synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object. With respect to FIG. 1, a process of acquiring an object lock will be described. The process of acquiring an object lock begins at step 104 where a thread obtains the object on which the thread wishes to operate. In general, the object on which the thread intends to operate has an associated object lock. Then, in step 106, a determination is made regarding whether the object is locked. That is, a determination is made regarding whether the object lock associated with the object is held by another thread, e.g., a thread that is currently operating on the object.
If the determination in step 106 is that the object is not locked, then the thread acquires the object lock in step 108. Alternatively, if the object is locked, then the thread waits for the object to be unlocked in step 110. Once the object is unlocked, process flow moves from step 110 to step 108 where the object is locked by the thread.
As previously mentioned, a thread is permitted to execute a synchronized operation on an object if it successfully acquires the lock on the object. While one thread holds the lock on an object, other threads may be allowed to attempt to execute additional synchronization operations on the object, and may execute non-synchronized operations on the object. Thread synchronization is a process by which threads may interact to check the status of objects, whether the objects are locked or unlocked, while allowing only the thread which holds an object lock to execute synchronized operations on the locked object. Thread synchronization also enables threads to obtain and remove object locks.
When threads are synchronized, in order to make certain that only the thread that possesses an object lock is allowed to operate on a locked object, synchronization constructs are generally provided. One such synchronization construct is known in the art as the monitor. Monitors are simple yet fundamental thread synchronization constructs used in, for example, the JAVA(trademark) platform of the Sun Microsystems Corporation of Palo Alto, Calif. Typically, monitors are implemented using low-level synchronization primitives such as mutexes and the like. Even though programs may perform monitor operations on any object, it is generally too space inefficient to include a monitor implementation for every object. One alternative to having every object have its own monitor is to maintain a hash table that maps objects to monitors. Unfortunately, the use of hash tables introduces additional overhead in monitor lookup as well as causing multiple threads to contend for the access to the global hash table. However, even the use of hash tables can result in substantial overhead in those situations where only a small number of monitor operations are invoked.
Since experience has shown that the majority of monitor operations do not contend with monitor operations performed by other threads, one attempt at improving monitor utilization utilizes a small number of bits in the object header to handle the non-contended monitor operations. One such implementation, referred to as a xe2x80x9cthin lockxe2x80x9d, or lightweight monitor, is described in xe2x80x9cThin Locks: Featherweight Synchronization for Javaxe2x80x9d by David F. Bacon et al. (1998), 258-268 which is incorporated by reference in its entirety. As described, the lightweight monitor is formed of bits reserved in the object header that identifies which thread, in the form of a thread ID, owns the lightweight monitor and therefore has locked the associated object. In the case when monitor contention does occur, the virtual machine allocates a heavyweight monitor for the contended object.
FIG. 2a is a diagrammatic representation of the interface between a thread, an object, and a monitor in an object based system. A thread 202 attempts to execute the synchronization operation on an object 204 having a header 206. In order to execute synchronization operation, the thread 202 must first determine if the object 204 is owned by another thread and therefore unavailable, or locked. The thread 202 determines whether or not the object 204 is locked by entering a monitor 208 included in the object header 206. The monitor 208 represents either a lightweight monitor (otherwise referred to as a thin lock) or a pointer to a heavyweight monitor (also referred to as a fat lock). Generally, one bit in the monitor 208 (referred to as HEAVY_FLAG) indicates whether the monitor 208 is a lightweight monitor or a heavyweight monitor pointer. When the monitor is a lightweight monitor, the HEAVY_FLAG is set to xe2x80x9c0xe2x80x9d and, conversely, is the HEAVY_FLAG is set to xe2x80x9c1xe2x80x9d if it contains a heavyweight monitor pointer.
Typically, lightweight monitors are used for objects that are not subject to contention, i.e.; do not have wait, notify, or notifyALL operations performed upon them. The structure of a typical lightweight monitor 210 included in the object header 206 is shown in FIG. 2b. The lightweight monitor 210 includes a thread identifier 212, a nested lock count (recursion counter) 214, and a HEAVY_FLAG bit. In the situation where the thread identifier 212 (corresponding to the object 204) is zero, the associated object 204 is unowned and unlocked. If, however, the thread identifier 212 in not zero (i.e.; is a thread ID), it represents an index into a table that maps thread IDs to thread pointers. In this case, the thread ID stored in the thread identifier 212 points to the thread which owns the object 204.
In order to enter a monitor, the thread 202 typically performs a compare and swap operation on the monitor. In a compare and swap operation, the new value is the thread ID associated with the thread 202 and the comperand is zero. If the compare and swap operation is successful, the thread ID, recursion counter, and all flags (such as the HEAVY_FLAG) in the monitor 208 were all zero indicating that the monitor was unowned. After the compare and swap operation has been successfully completed, the monitor 208 holds the thread ID associated with the thread 202 which indicates the thread 202 now owns the monitor 208. In those cases where a thread is re-entering a monitor it already owns (i.e.; the monitor is re-entrant), the thread must first increment the recursion counter without causing the recursion counter to overflow. In the case where incrementing the recursion counter would result in an overflow condition, the thread must inflate the lightweight monitor into a heavyweight monitor with itself as owner. It should be noted that only current monitor owners are able convert a lightweight monitor to a corresponding heavyweight monitor. Typically, inflation is accomplished by performing a compare and swap operation on the object header with the new value being a heavyweight monitor pointer.
Assuming now that a second thread 216 subsequently attempts to lock the object 204 owned by the thread 202. As before, the thread 216 will attempt to enter the monitor 208 by performing a compare and swap. In this case, however, the operation will fail since the comperand is the thread ID associated with the thread 216 and the thread ID stored in the monitor 208 is that for the thread 202. Thread 216 will then check to see whether it has already locked the object 204, and this test will also fail indicating since the object 204 is locked by the thread 202. At this point, the monitor 208 is contended and in order for the thread 216 to execute a synchronous operation on the object 204, the thread 216 must force a conversion of the lightweight monitor to a heavyweight monitor. However, since this conversion can only be performed by the current monitor owner, i.e. thread 202, the thread 216 enters a spin-lock loop on the object 204. By spin lock loop, the thread 216 enters a wait queue until such time as the thread 202 unlocks the object 204 at which time it is available to the thread 216 (as well as any other threads). As well known in the art, spin locking in general is undesirable due in part to its inefficient use of system resources. Spin locking is especially inefficient in those cases where the object 204 is locked for a long period of time causing additional threads to spin lock on the object 204. In addition, xe2x80x9cstarvingxe2x80x9d low priority threads is a distinct possibility in those situations where higher priority threads are spin locked on the same object.
Therefore, what is desired is an efficient method and apparatus for converting a contended lightweight monitor into a heavyweight monitor in an object-based system that utilizes synchronized threads.
Broadly speaking, the invention relates to an improved method, apparatus and computer system for efficiently converting a lightweight monitor associated with a contended object into a heavyweight monitor. According to one aspect of the invention, for a first thread to execute a synchronous operation on an object owned by a second thread, the first thread creates a new heavyweight monitor and sets the second thread as owner of the newly created heavyweight monitor. The first thread then enters the heavyweight monitor. In this manner, the first thread is not required to spin lock until such time as the second thread unlocks the object.
The invention can be implemented in numerous ways, including as a method, a computer system, and an apparatus. Several embodiments of the invention are discussed below. Methods and apparatus are disclosed. According to one aspect of the present invention, a computer-implemented method for converting a lightweight monitor to a heavyweight monitor when an object owned by a second thread is unavailable to a first thread includes determining ownership of the object associated with the lightweight monitor. If it is determined that the second thread owns the object, the first thread creates a new heavyweight monitor. The first thread then sets second thread as the owner of the newly created heavyweight monitor. The first thread then enters the newly created heavyweight monitor.
According to yet another aspect of the present invention, a computer system includes a memory and a plurality of threads. The computer system also includes a processor coupled to the memory and an object that includes an object header, the object header being arranged to contain a lightweight monitor that includes information relating to the ownership of object. A first thread selected from the plurality of threads that has locked the object as indicated by a first thread ID included in the lightweight monitor; and a second thread selected from the plurality of threads, the second thread being arranged to convert the lightweight monitor to a corresponding heavyweight monitor owned by the first thread when the object is not available to the second thread.
According to still another aspect of the invention, a computer program product for converting a lightweight monitor into a heavy weight monitor when a first thread attempts to execute a synchronous operation on an object having an object header containing the lightweight monitor is disclosed. The computer program product includes computer code that determines ownership of the object, that creates a heavyweight monitor when it is determined that the object is owned by a second thread, that sets ownership of the heavyweight monitor to the second thread; and computer code that causes the first thread to enter the heavyweight monitor; and a computer readable medium that stores the computer codes.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.